/* Heapsort. 
   1. First convert the array into a binary heap. Each node is greater than
      it's children. The biggest element is now at the root.
   2. Swap root with the last element. i.e. The biggest is in it's place. 
   3. Heapify the array again upto n-1 
   4. Do steps 2-3 until heap size is 1 */
#include <stdio.h>


void swap(int *x, int *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

void print_arr(int arr[], int n)
{
    int i = 0;

    for (i = 1; i<=n; i++)
    {
        printf("%4d ", arr[i]);
    }

    printf("\n");
}


/* sift_down ensures the heap property applies at the final position of a value
 * that was at start in the beginning. It moves it down the heap until true */
void sift_down(int arr[], int start, int end)
{
    int cur = start;
    int child;

    while ( cur<=end/2)
    {
        child = cur*2;
        if ((child < end) && arr[child + 1] > arr[child])
        {
            child = child + 1;
        }

        if (arr[cur] < arr[child])
        {
            swap(&arr[cur], &arr[child]);
            cur = child;
        }
        else
        {
            break;
        }
    }
}

void heapify(int arr[], int n)
{
    int i;

    for ( i=n/2; i>=1; i--)
    {
        print_arr(arr, n);
        sift_down(arr, i, n);
    }
}


void heap_sort(int arr[], int n)
{
    int end = n;
    heapify(arr, n);

    while (end > 1)
    {
        print_arr(arr, n);
        swap(&arr[1], &arr[end]);
        heapify(arr, end-1);
        end--;
    }
}


int main(void)
{
    int arr[] = { 9999, 22, 13, 43, 67, 7, 4, 15, 81, 46, 64, 8, 17, 18, 93 };
    int size = sizeof(arr)/sizeof(arr[0]);

    heapify(arr, size - 1);

    heap_sort(arr, size - 1);
    print_arr(arr, size - 1);

    return 0;
}


